package cn.edu.buaa.treehole.common;

@SuppressWarnings("unchecked")
public class LimitPriorityHeap<T extends Comparable<T>> {
    private final int capacity;
    private int size = 0;
    private final Object[] data;

    public LimitPriorityHeap(int capacity) {
        this.capacity = capacity;
        data = new Object[capacity];
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }

    public void enqueue(T element) {
        int c;
        if (size == capacity) {
            data[size - 1] = element;
            c = size - 1;
        }
        else {
            c = size++;
            data[c] = element;
        }
        int p = (c - 1) / 2;
        while (c != 0) {
            if (((T)data[p]).compareTo((T) data[c]) <= 0) {
                break;
            }
            swap(p, c);
            c = p;
            p = (c - 1) / 2;
        }
    }

    public T peek() {
        return (T) data[0];
    }

    public T dequeue() {
        T ret = (T) data[0];
        data[0] = data[--size];
        int p = 0;
        while (p < size) {
            int lc = 2 * p + 1;
            int rc = 2 * p + 2;
            if (((T) data[p]).compareTo(((T) data[lc])) <= 0) {
                if (((T) data[p]).compareTo((T) data[rc]) <= 0) {
                    return ret;
                }
                swap(p, rc);
                p = rc;
            }
            else {
                if (((T) data[lc]).compareTo((T) data[rc]) <= 0) {
                    swap(p, lc);
                    p = lc;
                }
                else {
                    swap(p, rc);
                    p = rc;
                }
            }
        }
        return ret;
    }

    private void swap(int i, int j) {
        T tmp = (T) data[i];
        data[i] = data[j];
        data[j] = tmp;
    }
}
